<html xmlns="http://www.w3.org/1999/xhtml"
	xmlns:h="http://java.sun.com/jsf/html"
	xmlns:f="http://java.sun.com/jsf/core"
	xmlns:ui="http://java.sun.com/jsf/facelets"
	xmlns:p="http://primefaces.org/ui">
<ui:composition template="/pages/templates/default.xhtml">
	<ui:define name="conteudo">
		<f:view>
			<p align="left">
				Criado em 1947 por George B. Dantzig, o método simplex pode ser
				considerado a ferramenta básica da programação linear. O espaço de
				buscas limitado pelas restrições é conhecido como região simplex,
				sendo que o algoritmo faz sua busca pela solução ótima nos pontos
				extremos dessa região. O algoritmo simplex utiliza-se de uma matriz,
				também conhecida como tableau, tentando levá-la a um certo padrão
				que nos trará a solução ótima. <br />Podemos dividí-lo em 5 passos:
				<br /> ● Adicionar as variáveis de folga <br /> ● Encontrar a
				variável não básica a entrar na base <br /> ● Encontrar a variável
				básica a sair da base. <br />● Recalcular os valores das linhas. <br />
				● Verificar a solução obtida, caso seja a solução ótima o algoritmo
				encerra a execução, caso contrário, retorna ao passo 2. <br /> <br />
				<b>Sequência de passos do algoritmo</b> <br /> <br />Passo 1:
				Adicionar as variáveis de folga. As restrições formam um conjunto de
				inequações, porém, para utilizar o método simplex precisamos
				transformá-las em equações. Fazemos isso incluindo uma variável de
				folga para cada restrição. É importante salientar que a partir de
				agora não precisamos da restrição de não-negatividade, pois o método
				de resolução do simplex já garante que os valores serão positivos.
				Também deveremos igualar à função objetivo a zero, passando seus
				termos para o lado esquerdo da igualdade e invertendo os respectivos
				sinais. Teremos então o seguinte modelo: <br />Z - 50x1 - 40x2 = 0
				<br />30x1 + 10x2 + f1 = 360 <br />5x1 + 10x2 + f2 = 120 <br />x1
				+ f3 =20<br /> <br />Montaremos então uma matriz com a função
				objetivo, restrições, variáveis de folga e o lado direito das
				equações: <br />
				<p:graphicImage value="/resources/images/matriza.jpg"></p:graphicImage>
				<br /> Passo 2: Encontrar a variável não básica a entrar na base. A
				variável que deverá entrar na base é a variável da linha da função
				objetivo que possuir o menor coeficiente, neste caso X1. A coluna da
				variável a entrar é chamada de coluna pivô.<br /> <br />Passo 3:
				Encontrar a variável básica a sair da base. Para isso precisamos
				calcular os quocientes, dividindo o valor do lado direito (LD) por
				seu respectivo coeficiente da coluna pivô. Fazendo isso obteremos
				para as linhas 1,2 e 3 os valores 12, 24 e 20, respectivamente. A
				variável que sairá será a que possuir o menor quociente positivo. A
				linha em que está essa variável é chamada de linha pivô. Devemos
				ficar atentos a um detalhe: se algum coeficiente da coluna pivô for
				negativo ou zero a linha deve ser desconsiderada no cálculo, pois
				esta não atende às restrições. <br /> <br />Passo 4: Recalcular os
				valores das linhas. Neste passo encontraremos os novos valores para
				cada coeficiente da matriz. Faremos isso utilizando a seguinte
				fórmula: <br /> <br /> Xij = Xij – Xic x (Xij / Xic) <br /> <br />Onde
				Xij é o coeficiente a ser recalculado e Xic é o número pivô, ou
				seja, é o coeficiente que está na coluna pivô. Esse passo também é
				conhecido como pivoteamento. Fazendo isso chegaremos à seguinte
				matriz: <br />
				<p:graphicImage value="/resources/images/matrizb.jpg"></p:graphicImage>
				<br />Passo 5: Verificar a solução obtida. Até este ponto temos que
				X1 é igual a 12, X2 é igual a zero, pois não se encontra nas linhas
				da base, e o valor total da função objetivo é igual a 600. Agora
				verificamos o critério de parada do algoritmo, que consiste em
				verificar se a solução ótima foi encontrada. A solução ótima foi
				encontrada se na linha da função objetivo não haver mais nenhuma
				variável com valor negativo, o que não aconteceu neste caso, pois
				temos que X2 é igual a -6,66. O algoritmo então retornará ao passo 2
				para sua segunda iteração, onde a matriz resultante será a seguinte
				<br />
				<p:graphicImage value="/resources/images/matrizc.jpg"></p:graphicImage>
				<br />Neste momento chegamos à solução ótima, pois não há mais
				nenhuma variável com coeficiente negativo na linha da função
				objetivo. A solução encontrada foi: X1 = 6 e X2 = 9, alcançando um
				total de 660 da função objetivo. É importante ficarmos atentos a
				sempre começarmos os cálculos pela variável de menor valor na linha
				da função objetivo, para garantirmos que a solução ótima será
				encontrada com o menor número de iterações possível. <br /> <BR />
				<B>Método simplex das duas fases</B> <br /> <BR />O método simplex
				é iniciado sempre a partir de uma solução inicial viável. Em
				problemas como o do exemplo anterior, que possuem apenas restrições
				de “&lt;=”, está solução sempre existirá. Entretanto, quando o
				problema possui restrições de “&gt;=” ou “=” essa solução inicial
				não existirá, devido a inexistência de folgas positivas na equação.
				Como não existe uma solução inicial viável não é possível iniciar o
				método simplex. Para nos livrarmos deste empecilho, precisamos
				utilizar alguma técnica que acondicione a matriz do tableau, de modo
				que nos possibilite chegar a uma solução viável inicial. As técnicas
				mais conhecidas para isto são o método Big M, que consiste em um
				método de penalização, e o método simplex das duas fases, sendo que
				utilizaremos o método das duas fases. <br /> <BR />O método das
				duas fases consiste em executar uma fase inicial para chegar a uma
				solução inicial viável e poder, assim, dar início ao simplex. A
				primeira fase consiste em resolver o problema usando uma função
				objetivo artificial, compatível com o problema original. Antes de
				construirmos a nova função objetivo precisamos alterar as restrições
				adicionando uma variável artificial em cada restrição que possuir
				sinal de “=” ou “&lt;=”. Vale lembrar que essas variáveis não fazem
				parte do problema, são apenas um artifício matemático para podermos
				chegar a uma solução viável inicial, e que possuem valor positivo. <br />
				<BR />Após adicionarmos as variáveis artificiais montaremos a
				função objetivo da primeira fase, que consiste na soma das
				restrições que possuem variáveis artificiais. Damos início, então, à
				execução do método simplex, tendo como base a função objetivo da
				primeira fase. Fazendo isso buscamos anular as variáveis artificiais
				da base. <br /> <BR />Se ao final da primeira fase as variáveis
				artificiais forem anuladas, pode-se remover a função objetivo
				artificial, junto com todas as variáveis artificiais e dar início à
				execução normal do simplex, caso contrário, problema original não
				possui solução viável. <br /> <br /> <b>O algoritmo branch and
					bound</b> <br /> <br />O algoritmo branch-and-bound(expandir e
				limitar, em tradução livre) é um método de enumeração que é
				utilizado juntamente com o método simplex para a resolução de
				problemas de programação inteira e mista. Desenvolvido originalmente
				por A.H. Land e A.G, o algoritmo envolve a divisão da área de
				soluções viáveis em áreas menores, até que se encontre uma solução
				que maximize(ou minimize) o problema original (Shenoy, 1986). <br />
				<br />Devemos iniciar o branch-and-bound ao final do método
				simplex, quando desejamos obter valores discretos para as variáveis
				e estes não foram obtidos naturalmente pela execução do simplex. O
				algoritmo consiste em adicionar novas restrições ao problema
				original, a fim de remover os valores contínuos da solução. Tais
				restrições são criadas se estabelecendo um limite superior e
				inferior para as variáveis que devem ser discretas. Escolheremos uma
				variável, que será definida como variável de separação, e através
				dela expandiremos o problema em dois novos subproblemas, um com
				restrição superior e outro com restrição inferior. <br /> <br />Supomos
				que ao final da execução do método simplex obtemos para a variável A
				o valor de 5.6, criaremos então um novo problema adicionando a
				restrição A &lt;= 5 (limite inferior), e um novo problema
				adicionando a restrição A &gt;= 6 (limite superior) e os
				resolveremos novamente utilizando o método simplex. Repetiremos este
				processo para todas as possibilidades, buscando assim, a melhor
				solução inteira para o problema. <br /> <br />A desvantagem deste
				método é o alto custo computacional, pois podemos precisar resolver
				vários problemas para chegar à solução do problema original.

			</p>
		</f:view>
	</ui:define>
</ui:composition>
</html>
